#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

'''
arr中只有一种数，出现奇数次
'''
from functools import reduce
def print_odd_times_num1(arr: list) -> int:
#    return reduce(lambda x,y: x^y, arr)
    eor = 0
    for i in arr:
        eor ^= i
    return eor

'''
arr中有两种数，出现奇数次
'''
def print_odd_times_num2(arr: list) -> list:
    eor = reduce(lambda x,y: x^y, arr)
    right_only = eor & (~eor + 1) # 提取eor里面最右边的1
    only_one = 0
    for i in arr:
        if i & right_only != 0: # 说明i里面的那一位（right_only）也是1，
            only_one ^= i
    return [only_one, only_one^eor]

'''
整数中1的个数
'''
def count(num: int) -> int:
    c = 0
    while num:
        num &= num - 1
        c += 1
    return c

def count1(num: int) ->int:
    c = 0
    while num:
        right_one = num & ((~num) + 1)  # 提取num里面最右边的1
        c += 1
        num ^= right_one     # 把最右边的1删除
    return c

'''
二分法找出某个数
'''
def exist(sorted_arr: list, num: int) -> bool:
    if not sorted_arr or len(sorted_arr) < 2: return False
    pl = 0
    pr = len(sorted_arr) -1
    while (pl < pr):
        mid = pl + ((pr -pl) >> 1)
        if sorted_arr[mid] == num: return True
        elif sorted_arr[mid] < num : pl = mid + 1
        else: pr = mid -1
    return sorted_arr[pl] == num  # 经过多次测试，pl就是最后剩下得值

#对数器
def compare_exist(sorted_arr: list, num: int) -> bool:
    if not sorted_arr or len(sorted_arr) < 2: return False
    for i in sorted_arr:
        if num == i:
            return True
    return False

'''
    在升序arr上查找 >=value的最左位置（1 2 3） 当value==2 时， index是2， 当value=4, 3, 当value==1, index=2
'''
def eindex(arr: list, value: int) -> int:
    if not arr : return -1
    pr = len(arr) -1
    index = -1
    pl = 0
    while pl <= pr:  #等于号是调试出来的
        mid = pl + ((pr - pl) >> 1)
        if arr[mid] >= value:  #所有大于等于的值都是潜在的index
            index = mid
            pr = mid -1
        else: pl = mid + 1
    return index
#对数器
def compare_eindex(arr: list, value: int) -> int:
    if not arr : return -1
    for i in range(len(arr)):
        if arr[i] >= value:
            return i
    return -1

'''
    在升序arr上查找<=value的最右位置（1 2 3）当value==2 时， index是1， 当value=4, index=3, 当value==1, index=-1
'''
def eindex1(arr: list, value: int) -> int:
    if not arr : return -1
    pr = len(arr) -1
    index = -1
    pl = 0
    while pl <= pr:  #等于号是调试出来的
        mid = pl + ((pr - pl) >> 1)
        if arr[mid] <= value:  #所有小于等于的值都是潜在的index
            index = mid
            pl = mid + 1
        else: pr = mid - 1
    return index
#对数器
def compare_eindex1(arr: list, value: int) -> int:
    if not arr : return -1
    i = len(arr) -1  #  range((len(arr)-1),-1,-1)  倒序
    while i >= 0:
        if arr[i] <= value:
            return i
        i -= 1
    return -1

'''
局部最小：数组的局部最小元素。编写一个程序，给定一个含有 N 个不同整数的数组，找到一个局部最小元素：
满足 a[i] < a[i-1]，且 a[i] < a[i+1] 的索引 i。程序在最坏情况下所需的比较次数为 ~ 2lgN。

相邻数组的元素必须互不相同：
如果数组的元素不能保证互不相同，不可能在O(lgn)时间内解决这个问题。因为如果这个数组全是1，那么必须要遍历数组中的所有元素才有可能确定不存在，至少是O(n)。
还有一点需要注意，
数组可能为空，或者只有一个元素或者两个元素。

'''
def get_less_index(arr: list) -> int:
    if not arr or len(arr) == 0: return -1
    if len(arr) == 1 or arr[0] < arr[1]: return 0
    tmp = len(arr) -1
    if arr[tmp] < arr[tmp - 1]: return tmp
    pl = 2
    pr = tmp -1 # 倒数第二元素
    while pl < pr:
        mid = pl + ((pr - pl) >> 1)
        if arr[mid] > arr[mid - 1]:
            pr = mid -1
        elif arr[mid] > arr[mid + 1]:
            pl = mid + 1
        else : return mid
    return pl #这个pl选的很重要
'''
a = [1,2,3,4,5,6,3]
b = [6,5,4,3,7,8,5]
c = [6,5,4]
print(get_less_index(a))
print(get_less_index(b))
print(get_less_index(c))
'''


'''
给定一个数组，左边都是< num, 右边都是>num, 请找出小于num的里面最右面的
'''

def get_less_right(arr: list, num: int) -> int:
    if not arr : return -1
    if len(arr) == 1 and arr[0] < num :
        return 0
    pl = 0
    pr = len(arr) - 1
    index = -1
    while pl <= pr :
        mid = pl + ((pr -pl) >> 1)
        if arr[mid] > num :
#            index = (mid - 1) if pl > 0 else -1
            pr = mid - 1
        elif arr[mid] < num:
            index = mid
            pl = mid + 1
    return index

#对数器

def compare_get_less_right(arr: list, num: int) -> int:
    if not arr : return -1
    if len(arr) == 1 and arr[0] < num :
        return 0
    for i in range(len(arr) - 1):
        if arr[i] < num and arr[i+1] >= num:
            index = i
            break
        else : index = -1
    if arr[len(arr) -1] < num: index = len(arr) -1
    return index
import random

def generate_random_array(max_size: int, max_value: int) -> list :
    length = random.randint(1, max_size )  #random.randint结果包括右边界
    arr = []
    for i in range(length):
        arr.append(random.randint(1, max_value))
    return arr

def copy_array(arr : list) -> list:
    if len(arr) == 0 : return None
# list2 = list1.copy()
    return arr[:]


def is_equal(arr1: list, arr2 : list) -> bool :

        if ((not arr1 and arr2) or (arr1 and not arr2)) :
            return False

        if (not arr1 and not arr2) :
            return True

        if (len(arr1) != len(arr2)) :
            return False

        for i in range(len(arr1)-1):
            return arr1[i] == arr2[i]


def print_array(arr : list) :
    if not arr: return
    print(arr)



def main():
    test_time = 500000
    max_size = 100
    max_value = 100
    succeed = True
    for i in range(test_time):
        arr1 = generate_random_array(max_size, max_value)
        arr1.sort()
#        arr2 = copy_array(arr1)
#        arr3 = copy_array(arr1)
        if compare_get_less_right(arr1, 30)!= get_less_right(arr1, 30) :
            succeed = False
            break
# 相当于三目运算
    print('Nice!' if succeed else 'Fucking fucked!')
    if succeed is False:
        print("get_less_right\n")
        print_array(arr1)
        print(compare_get_less_right(arr1, 30))
        print(get_less_right(arr1, 30))

if __name__ == "__main__":
     main()
